141. Linked List Cycle
Easy

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Accepted
947.2K
Submissions
2.2M
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.78 (259 votes)

Premium Video

Video Solution


 


Solution Article

This article is for beginners. It introduces the following ideas: Linked List, Hash Table and Two Pointers.



Approach 1: Hash Table

Intuition

To detect if a list is cyclic, we can check whether a node had been visited before. A natural way is to use a hash table.

Algorithm

We go through each node one by one and record each node's reference (or memory address) in a hash table. If the current node is null, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash table, then return true.

Complexity analysis

Let nn be the total number of nodes in the linked list.

  • Time complexity : O(n)O(n). We visit each of the nn elements in the list at most once. Adding a node to the hash table costs only O(1)O(1) time.

  • Space complexity: O(n)O(n). The space depends on the number of elements added to the hash table, which contains at most nn elements.


Approach 2: Floyd's Cycle Finding Algorithm

Intuition

Imagine two runners running on a track at different speed. What happens when the track is actually a circle?

Algorithm

The space complexity can be reduced to O(1)O(1) by considering two pointers at different speed - a slow pointer and a fast pointer. The slow pointer moves one step at a time while the fast pointer moves two steps at a time.

If there is no cycle in the list, the fast pointer will eventually reach the end and we can return false in this case.

Now consider a cyclic list and imagine the slow and fast pointers are two runners racing around a circle track. The fast runner will eventually meet the slow runner. Why? Consider this case (we name it case A) - The fast runner is just one step behind the slow runner. In the next iteration, they both increment one and two steps respectively and meet each other.

How about other cases? For example, we have not considered cases where the fast runner is two or three steps behind the slow runner yet. This is simple, because in the next or next's next iteration, this case will be reduced to case A mentioned above.

Complexity analysis

  • Time complexity : O(n)O(n). Let us denote nn as the total number of nodes in the linked list. To analyze its time complexity, we consider the following two cases separately.

    • List has no cycle:
      The fast pointer reaches the end first and the run time depends on the list's length, which is O(n)O(n).

    • List has a cycle:
      We break down the movement of the slow pointer into two steps, the non-cyclic part and the cyclic part:

      1. The slow pointer takes "non-cyclic length" steps to enter the cycle. At this point, the fast pointer has already reached the cycle. Number of iterations=non-cyclic length=N\text{Number of iterations} = \text{non-cyclic length} = N

      2. Both pointers are now in the cycle. Consider two runners running in a cycle - the fast runner moves 2 steps while the slow runner moves 1 steps at a time. Since the speed difference is 1, it takes distance between the 2 runnersdifference of speed\dfrac{\text{distance between the 2 runners}}{\text{difference of speed}} loops for the fast runner to catch up with the slow runner. As the distance is at most "cyclic length K\text{cyclic length K}" and the speed difference is 1, we conclude that
        Number of iterations=almost\text{Number of iterations} = \text{almost} "cyclic length K\text{cyclic length K}".

    Therefore, the worst case time complexity is O(N+K)O(N+K), which is O(n)O(n).

  • Space complexity : O(1)O(1). We only use two nodes (slow and fast) so the space complexity is O(1)O(1).

Report Article Issue

Comments: 141
lostandfoundii's avatar
Read More

Genius approach 2!!!

52
Reply
Share
Report
jianchao-li's avatar
Read More

The slow and fast points can also both start at head.

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

286
Show 16 replies
Reply
Share
Report
Argondey's avatar
Read More

I used a slightly faster destructive approach. I created a new node called "mark" and iterated through the list, setting the next value of each node to the mark node. When reaching the new node the first thing I did was check if the node is the mark node. If it ever is the mark node, we have looped.

67
Show 13 replies
Reply
Share
Report
asharma78901's avatar
Read More

The last algorithm is called 'Floyd's Tortoise and Hare'

139
Show 3 replies
Reply
Share
Report
leaping_tiger's avatar
Read More

What is the role of pos here? I'm so confused! Because if this variable is given at input (which seems like it is), then it gives away the answer. So, why do we have it and what do we do with it? Thank you.

37
Show 6 replies
Reply
Share
Report
jrico59's avatar
Read More

Very confused because in the Ruby version there is no "pos" input as mentioned in the description - only a head node.

8
Show 1 reply
Reply
Share
Report
monireh's avatar
Read More

What is role of pos in the problem description? Just to confuse the interview candidate?

18
Show 2 replies
Reply
Share
Report
cypherphage's avatar
Read More

Can someone please validate this answer. It passes the default test case, I don't know if its a fluke or not
I am new to leetcode

class Solution(object):
    def hasCycle(self, head):        
        nodes = {}
        while head != None:
            if head in nodes:
                return True            
            nodes[head] = head
            head = head.next                
        return False

11
Show 2 replies
Reply
Share
Report
Dr_Sean's avatar
Read More

Python3 code using two-pointers approach:

        if not head or not head.next: return False        
        slow, fast = head, head.next
        while slow != fast:
            if not fast or not fast.next: return False
            slow, fast = slow.next, fast.next.next
        return True

12
Show 3 replies
Reply
Share
Report
dayatar's avatar
Read More

Solution: time complexity : O(n), space 0(1)

Reverse a linked list, if you get the same head that means
the linked List has a cycle otherwise it doesn't

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False
        reverse_head = self.reverseList(head)
        if reverse_head is head:
            return True
        else:
            return False
    def reverseList(self, head):
        new_head = None
        while head:
            tmp = head.next
            head.next = new_head
            new_head = head
            head = tmp
            
        return new_head

10
Show 3 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/15/2021 09:06Accepted12 ms8 MBcpp
05/31/2021 19:23Accepted12 ms8.1 MBcpp
07/27/2020 08:27Accepted12 ms7.7 MBcpp
06/14/2020 15:51Wrong AnswerN/AN/Acpp
06/11/2020 11:46Accepted7 ms43.2 MBjava
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium